An Introduction to Formal Languages and Automata [6th ed.]

Contents......Page 3
Preface......Page 8
1 INTRO TO THEORY OF COMPUTATION......Page 11
Sets......Page 13
Functions and Relations......Page 16
Graphs and Trees......Page 18
Proof Techniques......Page 19
Languages......Page 27
Grammars......Page 30
Automata......Page 36
1.3 Some Applications*......Page 40
2 FINITE AUTOMATA......Page 47
2.1 Deterministic Finite Accepters......Page 48
Languages and Dfa’s......Page 51
Regular Languages......Page 56
Definition of a Nondeterministic Accepter......Page 61
Why Nondeterminism?......Page 65
2.3 Equivalence of Deterministic and Nondeterministic Finite Accepters......Page 68
2.4 Reduction of the Number of States in Finite Automata*......Page 76
3 REGULAR LANGUAGES & REGULAR GRAMMARS......Page 83
Formal Definition of a Regular Expression......Page 84
Languages Associated with Regular Expressions......Page 85
Regular Expressions Denote Regular Languages......Page 90
Regular Expressions for Regular Languages......Page 92
Regular Expressions for Describing Simple Patterns......Page 98
3.3 Regular Grammars......Page 101
Right- and Left-Linear Grammars......Page 102
Right-Linear Grammars Generate Regular Languages......Page 103
Right-Linear Grammars for Regular Languages......Page 106
Equivalence of Regular Languages and Regular Grammars......Page 107
4 PROPERTIES OF REGULAR LANGUAGES......Page 111
Closure under Simple Set Operations......Page 112
Closure under Other Operations......Page 115
4.2 Elementary Questions about Regular Languages......Page 124
Using the Pigeonhole Principle......Page 127
A Pumping Lemma......Page 128
5 CONTEXT-free LANGUAGES......Page 139
5.1 Context-Free Grammars......Page 140
Examples of Context-Free Languages......Page 141
Leftmost and Rightmost Derivations......Page 143
Derivation Trees......Page 144
Relation Between Sentential Forms and Derivation Trees......Page 147
5.2 Parsing and Ambiguity......Page 150
Parsing and Membership......Page 151
Ambiguity in Grammars and Languages......Page 155
5.3 Context-Free Grammars and Programming Languages......Page 161
6 SIMPLIFICATION OF CONTEXT-free GRAMMARS & NORMAL FORMS......Page 164
6.1 Methods for Transforming Grammars......Page 165
A Useful Substitution Rule......Page 166
Removing Useless Productions......Page 168
Removing λ-Productions......Page 172
Removing Unit-Productions......Page 174
Chomsky Normal Form......Page 180
Greibach Normal Form......Page 183
6.3 A Membership Algorithm for Context-Free Grammars*......Page 187
7 PUSHDOWN AUTOMATA......Page 190
7.1 Nondeterministic Pushdown Automata......Page 191
Definition of a Pushdown Automaton......Page 192
The Language Accepted by a Pushdown Automaton......Page 195
Pushdown Automata for Context-Free Languages......Page 200
Context-Free Grammars for Pushdown Automata......Page 205
7.3 Deterministic Pushdown Automata and Deterministic Context-Free Languages......Page 212
7.4 Grammars for Deterministic Context-Free Languages*......Page 216
8 PROPERTIES OF CONTEXT-free LANGUAGES......Page 221
A Pumping Lemma for Context-Free Languages......Page 222
A Pumping Lemma for Linear Languages......Page 227
Closure of Context-Free Languages......Page 231
Some Decidable Properties of Context-Free Languages......Page 235
9 TURING MACHINES......Page 239
Definition of a Turing Machine......Page 240
Turing Machines as Language Accepters......Page 247
Turing Machines as Transducers......Page 250
9.2 Combining Turing Machines for Complicated Tasks......Page 257
9.3 Turing’s Thesis......Page 263
10 OTHER MODELS OF TURING MACHINES......Page 267
Equivalence of Classes of Automata......Page 268
Turing Machines with a Stay-Option......Page 269
Turing Machines with Semi-Infinite Tape......Page 271
The Off-Line Turing Machine......Page 273
Multitape Turing Machines......Page 276
Multidimensional Turing Machines......Page 279
10.3 Nondeterministic Turing Machines......Page 281
10.4 A Universal Turing Machine......Page 284
10.5 Linear Bounded Automata......Page 289
11 HIERARCHY OF FORMAL LANGUAGES & AUTOMATA......Page 293
11.1 Recursive and Recursively Enumerable Languages......Page 294
Languages That Are Not Recursively Enumerable......Page 296
A Language That Is Not Recursively Enumerable......Page 297
A Language That Is Recursively Enumerable but Not Recursive......Page 299
11.2 Unrestricted Grammars......Page 301
11.3 Context-Sensitive Grammars and Languages......Page 307
Context-Sensitive Languages and Linear Bounded Automata......Page 308
Relation Between Recursive and Context-Sensitive Languages......Page 310
11.4 The Chomsky Hierarchy......Page 313
12 LIMITS OF ALGORITHMIC COMPUTATION......Page 316
Computability and Decidability......Page 317
The Turing Machine Halting Problem......Page 318
Reducing One Undecidable Problem to Another......Page 322
12.2 Undecidable Problems for Recursively Enumerable Languages......Page 326
12.3 The Post Correspondence Problem......Page 330
12.4 Undecidable Problems for Context-Free Languages......Page 336
12.5 A Question of Efficiency......Page 339
13 OTHER MODELS OF COMPUTATION......Page 342
13.1 Recursive Functions......Page 344
Primitive Recursive Functions......Page 345
Ackermann’s Function......Page 349
μ Recursive Functions......Page 350
13.2 Post Systems......Page 353
Matrix Grammars......Page 357
Markov Algorithms......Page 358
L-Systems......Page 360
14 OVERVIEW OF COMPUTATIONAL COMPLEXITY......Page 362
14.1 Efficiency of Computation......Page 363
14.2 Turing Machine Models and Complexity......Page 365
14.3 Language Families and Complexity Classes......Page 369
14.4 The Complexity Classes P and NP......Page 372
14.5 Some NP Problems......Page 374
14.6 Polynomial-Time Reduction......Page 377
14.7 NP-Completeness and an Open Question......Page 380
A.1 A General Framework......Page 383
A.2 Mealy Machines......Page 384
A.3 Moore Machines......Page 386
A.4 Moore and Mealy Machine Equivalence......Page 388
A.5 Mealy Machine Minimization......Page 392
A.6 Moore Machine Minimization......Page 397
A.7 Limitations of Finite-State Transducers......Page 398
JFLAP  Tool......Page 401
Answers......Page 403
Refs......Page 445
Index......Page 446